/*
 * $Id: HashList.h,v 1.15 2006-05-02 05:58:55 bacon Exp $
 */

#ifndef _XPP_BAS_HASHLIST_CLASS_
#define _XPP_BAS_HASHLIST_CLASS_

#include <xp/types.h>
#include <xp/bas/assert.h>
#include <xpp/Hashable.h>
#include <xpp/bas/LinkedList.h>

namespace xpp
{
	namespace bas
	{

		template <typename T> class HashList
		{
		public:
			typedef LinkedList<T> DatumList;
			typedef typename DatumList::Node Node;

			HashList (
				xp_size_t node_capacity = 10, 
				xp_size_t load_factor = 75, 
				xp_size_t mpb_size = 0)/*: datum_list (mpb_size)*/
			{
				this->nodes = XP_NULL;
				this->node_capacity = 0;
				this->datum_list = XP_NULL;

				try {
					this->nodes = new Node*[node_capacity << 1];
					this->node_capacity = node_capacity;
					for (xp_size_t i = 0; i < node_capacity << 1; i++) {
						this->nodes[i] = XP_NULL;
					}

					this->datum_list = new LinkedList<T> (mpb_size);
				}
				catch (...) {
					if (this->nodes != XP_NULL) {
						delete[] this->nodes;
						this->node_capacity = 0;
						this->nodes = XP_NULL;
					}

					if (this->datum_list != XP_NULL) {
						delete this->datum_list;
						this->datum_list = XP_NULL;
					}
					throw;
				}

				this->load_factor = load_factor;
				this->threshold   = node_capacity * load_factor / 100;
			}

			HashList (const HashList<T>& list)/*: 
				datum_list (list.datum_list.mpBlockSize()) */
			{
				this->nodes = XP_NULL;
				this->node_capacity = 0;
				this->datum_list = XP_NULL;

				try {
					this->nodes = new Node*[list.node_capacity << 1];
					this->node_capacity = list.node_capacity;
					for (xp_size_t i = 0; i < list.node_capacity << 1; i++) {
						this->nodes[i] = XP_NULL;
					}

					this->datum_list = new LinkedList<T> (list.datum_list->mpBlockSize());
				}
				catch (...) {
					if (this->nodes != XP_NULL) {
						delete[] this->nodes;
						this->node_capacity = 0;
						this->nodes = XP_NULL;
					}
					if (this->datum_list != XP_NULL) {
						delete this->datum_list;
						this->datum_list = XP_NULL;
					}
					throw;
				}

				this->load_factor = list.load_factor;
				this->threshold   = list.threshold;

				for (xp_size_t i = 0; i < list.node_capacity; i++) {
					xp_size_t head = i << 1;
					xp_size_t tail = head + 1;

					Node* np = list.nodes[head];
					if (np == XP_NULL) continue;
					
					do {
						copy_datum (
							np, this->node_capacity, 
							this->nodes, this->datum_list);
						if (np == list.nodes[tail]) break;
						np = np->forward ();
					} while (1);
				}
			}

			~HashList ()
			{
				this->clear ();
				if (this->nodes != XP_NULL) delete[] this->nodes;
				if (this->datum_list != XP_NULL) delete this->datum_list;
			}

			HashList<T>& operator= (const HashList<T>& list)
			{
				this->clear ();

				for (xp_size_t i = 0; i < list.node_capacity; i++) {
					xp_size_t head = i << 1;
					xp_size_t tail = head + 1;

					Node* np = list.nodes[head];
					if (np == XP_NULL) continue;
					
					do {
						copy_datum (
							np, this->node_capacity, 
							this->nodes, this->datum_list);
						if (np == list.nodes[tail]) break;
						np = np->forward ();
					} while (1);
				}

				return *this;
			}

			Node* set (const T& datum, bool overwrite = true)
			{
				xp_size_t hc, head, tail;
				Node* np;

				hc = datum.hashCode() % node_capacity;
				head = hc << 1; tail = head + 1;

				np = nodes[head];
				if (np != XP_NULL) {
					do {
						T& t = np->value;
						if (datum == t) {
							if (!overwrite) return XP_NULL;

							t = datum;	
							return np;
						}

						if (np == nodes[tail]) break;
						np = np->forward ();
					} while (1); 
				}
				
				if (datum_list->size() >= threshold) {
					rehash ();
					hc = datum.hashCode() % node_capacity;
					head = hc << 1; tail = head + 1;
				}

				if (nodes[head] == XP_NULL) {
					nodes[head] =
						datum_list->insertDatum (XP_NULL, datum);
					nodes[tail] = nodes[head];
				}
				else {
					nodes[head] = 
						datum_list->insertDatum (nodes[head], datum);
				}
				return nodes[head];
			}

			T* setValue (const T& datum, bool overwrite = true)
			{
				// identical to setValue except that it returns 
				// the pointer to the value
				return &set(datum, overwrite)->value;
			}

			Node* nodeOf (const T& datum)
			{
				xp_size_t hc, head, tail;
				Node* np;

				hc = datum.hashCode() % node_capacity;
				head = hc << 1; tail = head + 1;

				np = nodes[head];
				if (np != XP_NULL) {
					do {
						T& t = np->value;
						if (datum == t) return np;
						if (np == nodes[tail]) break;
						np = np->forward ();
					} while (1);
				}

				return XP_NULL;
			}

			const Node* nodeOf (const T& datum) const
			{
				xp_size_t hc, head, tail;
				Node* np;

				hc = datum.hashCode() % node_capacity;
				head = hc << 1; tail = head + 1;

				np = nodes[head];
				if (np != XP_NULL) {
					do {
						T& t = np->value;
						if (datum == t) return np;
						if (np == nodes[tail]) break;
						np = np->forward ();
					} while (1);
				}

				return XP_NULL;
			}

			T* valueOf (const T& datum)
			{
				Node* b = nodeOf (datum);
				if (b == XP_NULL) return XP_NULL;
				return &b->value;
			}

			const T* valueOf (const T& datum) const
			{
				const Node* b = nodeOf (datum);
				if (b == XP_NULL) return XP_NULL;
				return &b->value;
			}

			bool contains (const T& datum) const
			{
				return nodeOf (datum) != XP_NULL;
			}

			int remove (const T& datum)
			{
				xp_size_t hc, head, tail;
				Node* np;

				hc = datum.hashCode() % node_capacity;
				head = hc << 1; tail = head + 1;

				np = nodes[head];
				if (np != XP_NULL) {
					do {
						T& t = np->value;
						if (datum == t) {
							if (nodes[head] == nodes[tail]) {
								xp_assert (np == nodes[head]);
								nodes[head] = nodes[tail] = XP_NULL;
							}	
							else if (np == nodes[head])
								nodes[head] = np->forward();
							else if (np == nodes[tail]) 
								nodes[tail] = np->backward();

							datum_list->remove (np);
							return 0;
						}

						if (np == nodes[tail]) break;
						np = np->forward ();
					} while (1);
				}

				return -1;
			}

			void clear ()
			{
				for (xp_size_t i = 0; i < (node_capacity << 1); i++) {
					this->nodes[i] = XP_NULL;
				}
				if (datum_list != XP_NULL) datum_list->clear ();
			}

			Node* head () const
			{
				return datum_list->head();
			}

			Node* tail () const
			{
				return datum_list->tail();
			}

			typedef int (HashList<T>::*TraverseCallback) (Node* start, Node* cur);

			void traverse (TraverseCallback callback, Node* start)
			{
				Node* cur, *backward, * forward;

				cur = start;
				while (cur != XP_NULL) {
					backward = cur->backward ();
					forward = cur->forward ();

					int n = (this->*callback) (start, cur);

					if (n > 0) cur = forward;
					else if (n < 0) cur = backward;
					else break;
				}
			}

			xp_size_t capacity() const
			{
				return node_capacity;
			}

			xp_size_t size () const
			{
				return datum_list->size();
			}

		protected:
			mutable xp_size_t node_capacity;
			mutable Node** nodes;
			mutable DatumList* datum_list;
			mutable xp_size_t threshold;
			xp_size_t load_factor;

			void rehash () 
			{
				HashList<T> temp (node_capacity << 1, load_factor, datum_list->mpBlockSize());
				Node* p = head();
				while (p != XP_NULL)
				{
					temp.set (p->value);
					p = p->forward ();
				}

				/* swap contents */
				xp_size_t temp_capa = temp.node_capacity;
				Node** temp_nodes = temp.nodes;
				DatumList* temp_datum_list = temp.datum_list;
				xp_size_t temp_threshold = temp.threshold;
				xp_size_t temp_load_factor = temp.load_factor;

				temp.node_capacity = node_capacity;
				temp.nodes = nodes;
				temp.datum_list = datum_list;
				temp.threshold = threshold;
				temp.load_factor = load_factor;

				node_capacity = temp_capa;
				nodes = temp_nodes;
				datum_list = temp_datum_list;
				threshold = temp_threshold;
				load_factor = temp_load_factor;

				/*
				xp_size_t new_node_capa = this->node_capacity << 1;
				Node** new_nodes = XP_NULL;

				try {
					new_nodes = new Node*[new_node_capa << 1];

					for (xp_size_t i = 0; i < new_node_capa << 1; i++) {
						new_nodes[i] = XP_NULL;
					}

					for (xp_size_t i = 0; i < this->node_capacity; i++) {
						xp_size_t head = i << 1;
						xp_size_t tail = head + 1;

						Node* np = this->nodes[head];
						if (np == XP_NULL) continue;

						T& t = np->value;
						xp_size_t nhc = t.hashCode() % new_node_capa;
						xp_size_t nhead = nhc << 1;
						xp_size_t ntail = nhead + 1;

						new_nodes[nhead] = this->nodes[head];
						new_nodes[ntail] = this->nodes[tail];
					}
				}
				catch (...) {
					if (new_nodes != XP_NULL) delete[] new_nodes;
					throw;
				}

				delete[] this->nodes;
				this->nodes = new_nodes;
				this->node_capacity = new_node_capa;

				this->threshold = 
					this->load_factor * this->node_capacity / 100;
				*/
			}

			void copy_datum (
				Node* np, xp_size_t new_node_capa,
				Node** new_nodes, DatumList* new_datum_list) const
			{
				T& t = np->value;

				xp_size_t hc = t.hashCode() % new_node_capa;
				xp_size_t head = hc << 1;
				xp_size_t tail = head + 1;

				if (new_nodes[head] == XP_NULL) {
					new_nodes[head] =
						new_datum_list->insertDatum (XP_NULL, t);
					new_nodes[tail] = new_nodes[head];
				}
				else {
					new_nodes[head] =
						new_datum_list->insertDatum (new_nodes[head], t);
				}
			}

		};

	}
}

#endif
